#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define false   0
#define true    1
#define  SIZE  256
#define  INIT 256
#define QSIZE  7
#define PSIZE  4
#define  HERE printf("%s: %d\n", __FILE__, __LINE__)
#define THERE printf("%d: %s\n", i, line)
#define CLEAR if (-1==system("clear")) system("cls")
#define PAUSE scanf("%c", &x)
#define DNE  -1

#define LD    1
#define ST    2

#define CALC 10
#define ADD  10
#define ADDI 11
#define SUB  20
#define SUBI 21

#define BRANCH 50
#define BRNZ   50
#define BRZ    51

char x;
int cpu_clock = 0;
int N     = 0;   // Total number of instructions to be executed.
int M[1000];  

struct Register {
  int lock;
  int val;
} R[32]; 

struct Instruction {
  char   *label;   
  char   *type;   
  int    index;
  int    is_busy;
  int    op_code;                
  int    R1, R2, R3;
  int    D[3];
  int    t_issue, 
         t_comp,
         t_wait;
} I[SIZE+1];

struct Load_Buffer {
  int I;
} buf[3];

struct Instruction_Queue {
  int head, tail, size;
  int I[QSIZE];
} Q;

struct Reservation_Station {
  int I[2];
};

struct ALU {
  struct Reservation_Station rs;
} alu[2];


void mark_incomplete(struct Instruction *I) {
  I->t_comp = DNE;
}

void reset_deps() {
  int i, j;
  for (i=0; i<SIZE; i++)  
    for (j=0; j<3; j++) {
      I[i].D[j]   = DNE; 
    }
}
 
// Initialize register and memory addresses to zero, and open all locks.
void reset () {
  int  i, j;
  for (i=0; i<32;   i++) { 
    R[i].val = 0; 
    R[i].lock=false; 
  }
  for (i=0; i<1000; i++) 
    M[i]     = 0; 
  init_alu_and_buf();
  reset_deps();
}

void wait (int ms) {
  clock_t endwait;
  endwait = clock () + ms * CLOCKS_PER_SEC/1000;
  while (clock() < endwait) {}
}

// Print instruction.
void print_instr (struct Instruction I) {
      if (I.is_busy) printf("!%d", I.t_wait);
      else           printf("--");
           if (I.op_code  < CALC) { printf("->:  %s R%d R%d;     \n", I.type, I.R1, I.R2      );
    } else if (I.op_code%10!=1)   { printf("->:  %s R%d R%d R%d; \n", I.type, I.R1, I.R2, I.R3);
    } else                        { printf("->:  %s R%d R%d #%d; \n", I.type, I.R1, I.R2, I.R3);
    }
}

// Print result of an ALU operation.
void print_result (struct Instruction I) {
  printf("--->:  %s R%d R%d R%d \t %d %d -> %d\n", I.type,   I.R1,        I.R2,        I.R3, 
                                                           R[I.R2].val, R[I.R3].val, R[I.R1].val);
}

// Print contents of instruction queue.
void print_instr_q() {
  int i;
  if (Q.size > 0)
  for (i=0; i<=QSIZE-1; i++)
          if (Q.head>=Q.tail && (i<=Q.head && i>=Q.tail)) print_instr(I[Q.I[i]]);
     else if (Q.head< Q.tail && (i>=Q.head && i<=Q.tail)) print_instr(I[Q.I[i]]);
     else    printf("--->:\n");
  else
  for (i=0; i<=QSIZE-1; i++)
     printf("--->:\n");
}

// Print contents of load buffer
void print_buf() {
  int a;
  for (a=0; a<=2; a++)
      print_instr(I[buf[a].I]);
}

// Print contents of reservation stations.
void print_rs() {
  int a, b;
  for (a=0; a<=1; a++)
    for (b=0; b<=1; b++)
      print_instr(I[alu[a].rs.I[b]]);
}

// Print all information for this cycle.
void print_state (char *message) {
    CLEAR;
    print_rs();
    printf("\n");
    print_buf();
    printf("\n");
    print_instr_q();
    printf("\n");
    printf("HEAD: %d\n", Q.head);
    printf("TAIL: %d\n", Q.tail);
    printf("SIZE: %d\n", Q.size);
    printf("TIME: %d\n", cpu_clock);
    printf("\n%s\n", message);
    wait(100);
}

// Assign wait times to instructions based upon operation.
void timestamp (struct Instruction *I) {
       if (I->op_code < CALC) I->t_wait = 3;
  else if (I->op_code < BRNZ) I->t_wait = 2;
  else if (I->op_code > BRNZ) I->t_wait = 2;
  else                        I->t_wait = 1;
}

void encode (struct Instruction *I) {
       if (0==strcmp(I->type, "ADD" ))  I->op_code = ADD;
  else if (0==strcmp(I->type, "SUB" ))  I->op_code = SUB;
  else if (0==strcmp(I->type, "ADDI"))  I->op_code = ADDI;
  else if (0==strcmp(I->type, "SUBI"))  I->op_code = SUBI;
  else if (0==strcmp(I->type, "ST"  ))  I->op_code = ST;
  else if (0==strcmp(I->type, "LD"  ))  I->op_code = LD;
  else if (0==strcmp(I->type, "BRNZ"))  I->op_code = BRNZ;
}

void load (struct Instruction *I) {
  R[I->R1].val = M[R[I->R2].val];
  R[I->R1].lock=false;
}

void store (struct Instruction *I) {
  M[R[I->R2].val] = R[I->R1].val; 
}

// Perform calculation inside of ALU.
// TODO: Make write-back asynchronous.
void calc (struct Instruction *I) {
  switch(I->op_code) {
    case ADD :  R[I->R1].val = R[I->R2].val + R[I->R3].val; break;
    case ADDI:  R[I->R1].val = R[I->R2].val +   I->R3     ; break;
    case SUB :  R[I->R1].val = R[I->R2].val - R[I->R3].val; break;
    case SUBI:  R[I->R1].val = R[I->R2].val -   I->R3     ; break;
    default  :  break;
  }
} 

// Detect the location of a branch.
int branch(struct Instruction *B) {
  int i;
  for (i=0; i<N; i++) 
    if (false==strcmp(B->label, 
                    I[i].label))
      return i;
  return DNE;
  printf("BRAN: %d\n", i);
}

// Read instructions from file into instruction array.
// Assign initial values for M[] and R[] as well.
struct Instruction *read_instr(FILE *infile) {
    int i;
    char  *line = malloc(SIZE);
    char *lline = malloc(SIZE);

    CLEAR;
    // Pre-processing stage.
    int idx,val;
    do { fgets( line, SIZE, infile);
         if (strstr(line, "##")) break;
         if (strstr(line, "=" )) {
            if (strstr(line, "M")) { sscanf(line, "M[%d] = %d", &idx, &val);  M[idx]     = val; printf(" INIT:  M[%3d] = %3.d\n", idx, M[idx]);  
          } else                   { sscanf(line, "R%d = %d",   &idx, &val);  R[idx].val = val; printf(" INIT:  R[%3d] = %3.d\n", idx, R[idx].val); 
          }
         }
         else printf(" ?-->:  %s", line);
    } while (!feof(infile)); 
    printf("\n");
    PAUSE; CLEAR;
  
    // Main stage, encodes instructions.
    for (i=0; i<=SIZE; i++) { 
      I[i].type  = malloc(SIZE);
      I[i].label = malloc(SIZE); 
    }
    i=0;
    int j=0;
    do { fgets(line, SIZE, infile);
      // Store label, if it exists.
        if (lline=strstr(line, ":"))  { 
          sscanf(line, "%[^:]", I[i].label); 
          j=-1;
          do {
            j++;
            if (lline[j] == ':') lline[j] = ' ';
            else                 lline[j] = lline[j];
          } while (lline[j]!='\n');
          strcpy(line, lline);
      } else { 
      }

      // Read instructions.
             if (      strstr(line, "##" )) { break; 
      } else if (NULL!=strstr(line, "LD"  ) 
             || (NULL!=strstr(line, "ST"))) { sscanf(line, "%s R%d R%d",     I[i].type, &I[i].R1, &I[i].R2);          
      } else if (NULL!=strstr(line, "BRN")) { sscanf(line, "%s R%d %[^ ]",   I[i].type, &I[i].R1, I[i].label);
      } else if (NULL!=strstr(line, "#"  )) { sscanf(line, "%s R%d R%d #%d", I[i].type, &I[i].R1, &I[i].R2, &I[i].R3); 
      } else                                { sscanf(line, "%s R%d R%d R%d", I[i].type, &I[i].R1, &I[i].R2, &I[i].R3); 
      } encode(&I[i]);
        I[i].index = i;
  
             if (I[i].op_code == LD  ) { printf(" MAIN:  %s\tR%d R%d\n",     I[i].type, I[i].R1, I[i].R2);         
      } else if (I[i].op_code == ST  ) { printf(" MAIN:  %s\tR%d R%d\n",     I[i].type, I[i].R1, I[i].R2);        
      } else if (I[i].op_code  < CALC) { printf(" MAIN:  %s\tR%d R%d\n",     I[i].type, I[i].R1, I[i].R2);
      } else if (I[i].op_code  >=BRNZ) { printf(" MAIN:  %s\tR%d %s",        I[i].type, I[i].R1, I[i].label);
      } else                           { printf(" MAIN:  %s\tR%d R%d R%d\n", I[i].type, I[i].R1, I[i].R2, I[i].R3, I[i].op_code); 
      } i++;
    } while (!feof(infile));
    printf("\n\n");

    N = i;
    free(line);
    return I;
}

// Handle post-process print requests. 
void post_process (FILE *infile) {
    int a, b, i=0;
    char *line = malloc(SIZE);
    do { fgets(line, SIZE, infile);
             if (      strstr(line, "##")) { break; 
      } else if (NULL!=strstr(line, "M[")) { sscanf(line, "M[%d-%d]", &a, &b); for(i=a; i<=b; i++) printf(" POST:  M[%3d] = %3.d\n", i, M[i]);
      } else if (NULL!=strstr(line, "R"))  { sscanf(line,   "R%d-%d", &a, &b); for(i=a; i<=b; i++) printf(" POST:  R[%3d] = %3.d\n", i, R[i].val);
      } else                               {
      }
      fgets(line, SIZE, infile);
    } while (!feof(infile));
    free(line);
    printf("\n");
}

// Handle post-process print requests from standard input. 
void post_process_stdin () {
    int a, b, i=0;
    char *line = malloc(SIZE);
    do {     
             printf("?> ");
             scanf("%s", line);
             if (      strstr(line, "##")) { break; 
      } else if (NULL!=strstr(line, "M[")) { sscanf(line, "M[%d-%d]", &a, &b); for(i=a; i<=b; i++) printf(" POST:  M[%3d] = %3.d\n", i, M[i]);
      } else if (NULL!=strstr(line, "M"))  { sscanf(line, "M%d",      &a    );                     printf(" POST:  M[%3d] = %3.d\n", a, M[a]);
      } else if (NULL!=strstr(line, "R[")) { sscanf(line, "R[%d-%d]", &a, &b); for(i=a; i<=b; i++) printf(" POST:  R[%3d] = %3.d\n", i, R[i].val);
      } else if (NULL!=strstr(line, "R"))  { sscanf(line, "R%d",      &a    );                     printf(" POST:  R[%3d] = %3.d\n", a, R[a].val);
      } else if (NULL!=strstr(line, "q"))     {  break;
      } else if (NULL!=strstr(line, "quit"))  {  break;
      } else if (NULL!=strstr(line, "exit"))  {  break;
      } else                                  { 
      }
    } while (line!=NULL);
    free(line);
    printf("\n");
}

// Lock a register while executing in ALU.
int lock(struct Instruction *I) {
  if (I->op_code != ST) R[I->R1].lock=true;
  else                  R[I->R2].lock=true;
}

// Unlock a register.
int unlock(struct Instruction *I) {
  if (I->op_code != ST) R[I->R1].lock=false;
  else                  R[I->R2].lock=false;
}

// Queue instructions into load buffer.
int enqueue (int i) {
    if (i<N) {
      int fittable = (Q.size <= QSIZE-PSIZE) ? PSIZE : QSIZE - Q.size;
      if (fittable < N-i) fittable=N-i;
      if (fittable > 0) {
        if (Q.tail==-1) Q.tail = 0;
        int j=0;
        for (j=0; j<fittable; j++) { 
          Q.I[(Q.tail+j)%QSIZE] = i+j;
          mark_incomplete(&I[i+j]);
        }
      Q.tail =(Q.tail+fittable-1)%QSIZE;
      i += fittable;
      Q.size+=fittable;
      }
    }
    dep_calc();
    return i;
}

// Issue an instruction to alu.
int issue_to_alu (struct Instruction *I, int a) {
  int b;
    for (b=0; b<=1; b++) 
      if (!I[alu[a].rs.I[b]].is_busy) {
           I->is_busy = true;
           I->t_issue = cpu_clock;
           timestamp(&I[alu[a].rs.I[b]]);
           return true;
      } 
  return false;
}

// Issue an instruction to load buffer.
int issue_to_buf(struct Instruction *I, int a) {
  int b;
    for (b=0; b<=2; b++) 
      if (!I[buf[b].I].is_busy) {
           I->is_busy = true;
           I->t_issue = cpu_clock;
           timestamp(&I[buf[b].I]);
           return true;
      } 
  return false;
}

// Issue all instructions to alu and load buffer.
int init_alu_and_buf () {
  int a, b;
  for (a=0; a<=1; a++) 
    for (b=0; b<=1; b++) 
      alu[a].rs.I[b] = INIT;
  for (a=0; a<=2; a++) 
      buf[a].I = INIT;
}

// Return false if some alu is open.
int alu_busy () {
  int a, b;
  for (a=0; a<=1; a++) 
    for (b=0; b<=1; b++) 
      if (!I[alu[a].rs.I[b]].is_busy) 
        return false;
  return true;
}

// Return false if some buf is open.
int buf_busy () {
  int a;
  for (a=0; a<=2; a++) 
      if (!I[buf[a].I].is_busy) 
        return false;
  return true;
}

// Issue all instructions to alu and load buffer.
int issue_all(int i) {
    if (Q.size > 0) {
     int a=0;
     while (I[Q.I[Q.head]].op_code>ST) {
       a = a==1 ? 0 : 1;
       if (true==issue_to_alu(&I[Q.I[Q.head]], a)) { 
         Q.head = (Q.head + QSIZE + 1) % QSIZE;
         if (Q.size > 0) Q.size--;
         if (i<N) i++; 
       } else break;
     }
     while (I[Q.I[Q.head]].op_code<ST) {
       if (true==issue_to_buf(&I[Q.I[Q.head]], a)) { 
         Q.head = (Q.head + QSIZE + 1) % QSIZE;
         if (Q.size > 0) Q.size--;
         if (i<N) i++; 
       } else break;
     }
    }
    return i;
}

// Check if dependencies are met.
void free_dependents (struct Instruction *I) {
  int i, j;
  for (i=0; i<N; i++)
    for (j=0; j<=2; j++) 
      if (I[i].D[j] == I->index) 
        I[i].D[j] = DNE;
}

// Check if dependencies are met.
int deps_met (struct Instruction *I) {
  int i;
  for (i=0; i<2; i++) 
    if (I->D[i] != DNE) 
      return false;
  return true;
}

// Check if registers are locked.
int lock_check(struct Instruction *I) {
          if (I->op_code == LD  ) { if (R[I->R2].lock==false) return true;
   } else if (I->op_code == ST  ) { if (R[I->R1].lock==false) return true; 
   } else if (I->op_code <  BRNZ) { if (R[I->R2].lock==false
                                     && R[I->R3].lock==false) return true;
   } else if (I->op_code >= BRNZ) { if (R[I->R1].lock==false) return true;
   } else                                                     return false;
   return false;
}

// Handle an individual instruction inside an ALU.
// TODO: If dependency not met, then cannot execute until it is.
int handle(struct Instruction *I) {
 int loc=DNE;
 if (I->is_busy==true) {
   if (deps_met(I)) {
    if (0==I->t_wait) {
            if (I->op_code == LD  ) {       load(I);  
     } else if (I->op_code == ST  ) {      store(I);  
     } else if (I->op_code <= BRNZ) {       calc(I);  
     } else if (I->op_code >= BRNZ) { loc=branch(I);  
     } else                         { printf("No such instruction\n");
     }
    I->is_busy=false;
    free_dependents(I);
  //unlock(I);
    } else {
    //lock(I);
      I->t_wait -= 1;
    }
  }
 }
 return loc;
}

// Handle instructions in the two ALUs and the load buffers.
int handle_all (i) {
  int a, b, br_status, branch=DNE;
  for (a=0; a<=2; a++)
      handle(&I[buf[a].I]);
  for (a=0; a<=1; a++)
    for (b=0; b<=1; b++) {
      br_status = handle(&I[alu[a].rs.I[b]]);
      if (br_status!=DNE) branch=br_status;
    }
  if (branch!=DNE) return branch;
  else             return i;
}

// Tell if instructions inside ALUs are finished executing.
int all_done() {
  int a, b;
  for (a=0; a<=1; a++)
    for (b=0; b<=1; b++) 
      if (I[alu[a].rs.I[b]].is_busy==true) return false;
  return true;
}

dep_assign (int i, int j) {
  int k;
  for (k=0; k<3; k++) 
    if (I[j].D[k] == DNE) { 
        I[j].D[k]  =   i;   break; }
}

// Calculate D for each instruction.
int dep_calc () {
 int i, j, k;
 for (i=0;   i<N-1; i++)
 for (j=i+1; j<N;   j++) 
       if (I[i].R1 == I[j].R1  && I[i].R1 != 0
       ||  I[i].R1 == I[j].R2  && I[i].R2 != 0
       ||  I[i].R1 == I[j].R3  && I[i].R3 != 0) dep_assign(i,j);
}

// Simulate the execution of instructions.
void simulate(struct Instruction *I) {
  int a,i=0; 
  int done;
  Q.head = 
  Q.size =   0;
  Q.tail =  -1;
  print_state("");
  PAUSE;

  do {
    cpu_clock++;

    if (i<=N) { i=enqueue(i); }
    print_state("");

    i=issue_all(i);
    print_state("");

    i==handle_all(i);
    print_state("");

    done = i>=N && Q.size<=0 && all_done();
    print_state("");

    PAUSE;
  } while (!done);

    print_state("Done");
    PAUSE;
}

int main (int argc, char **argv) {
  if (argc!=2) printf("Usage: %s [file]\n", argv[0]);

  FILE *infile;
  infile = fopen(argv[1], "r");

  // Initialize register and memory addresses.
  reset();
  CLEAR;

  // Load instruction set into array.
  struct Instruction *I = read_instr(infile);  
  PAUSE; 
  CLEAR;

  // Perform the simulation.
  simulate(I);
  CLEAR;

  // HAndle post-processing requests.
  post_process(infile);
  post_process_stdin();

  return 0;
}
